package cn.javadog.algorithm.m1_100;


import java.util.LinkedList;
import java.util.Objects;

/**
 * Z 字形变换
 * https://leetcode-cn.com/problems/zigzag-conversion/
 * @author Sprite
 */
public class Algorithm6 {
	public static void main(String[] args) {
		System.out.println(convert("LEETCODEISHIRING", 3));
		System.out.println(convert("LEETCODEISHIRING", 4));
		System.out.println(convert("AB", 1));
		System.out.println(convert("ABCD", 2));
	}

	public static String convert(String s, int numRows) {
		int length = s.length();
		if (length <= numRows || numRows == 1) return s;
		int xl = 0;
		int groupNum = length / (2 * numRows - 2);
		int groupNumLeft = length % (2 * numRows - 2);
		xl += groupNum * (numRows - 1);
		if (groupNumLeft <= numRows){
			xl += 1;
		}else {
			xl += groupNumLeft + 1 - numRows;
		}
		
		char[][] ccc = new char[numRows][xl];

		char[] cc = s.toCharArray();
		LinkedList<Character> queue = new LinkedList<>();
		for (char c : cc) queue.add(c);

		for (int i = 0; i < xl; i++) {
			for (int j = 0; j < numRows; j++) {
				if (i % (numRows-1) == 0 || i%(numRows-1)+j == numRows - 1){
					Character poll = queue.poll();
					if (Objects.isNull(poll)) break;
					ccc[j][i] = poll;
				}else {
					ccc[j][i] = '\0';
				}
			}
		}

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < numRows; i++) {
			for (int j = 0; j < xl; j++) {
				if (ccc[i][j] != '\0') sb.append(ccc[i][j]);
			}
		}
		return sb.toString();

	}
}
